#include <cstdio>
#include <cstring>
#define mod 1000000007
typedef long long ll;
using namespace std;
int n, t;
ll a[2][2] = {{1, 1}, {0, 0}};
struct Martri {
	ll f[2][2];
	Martri() {
		memset(f, 0, sizeof(f));
	}

	friend Martri operator*(const Martri &a, const Martri &b) {
		Martri res;
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				for (int k = 0; k < 3; ++k) {
					res.f[i][j] += a.f[i][k] * b.f[k][j] % mod;
					res.f[i][j] %= mod;
				}
		return res;
	}

public:
	void make() {
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				f[i][j] = a[i][j];
	};
};

Martri ans;

int main() {
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
	scanf("%d", &t);
	while (t--) {
		Martri b;
		b.make();
		scanf("%d", &n);
		ans.f[0][0] = 1;
		ans.f[0][1] = 1;
		ans.f[0][2] = 1;
		n = (n - 3) > 0 ? (n - 3) : 0;
		while (n) {
			if (n & 1) {
				ans = ans * b;
			}
			n >>= 1;
			b = b * b;
		}
		printf("%lld\n", ans.f[0][0]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}